Date: Tue, 14 Jan 1997 21:49:40 GMT
Server: NCSA/1.5.1
Last-modified: Sun, 06 Oct 1996 18:13:54 GMT
Content-type: text/html
Content-length: 17449


<title>
Design and Analysis of ATM Networks 
</title>

<h1> Design and Analysis of ATM Networks </h1>

<h3> Computer Networks Research Group<br>
in the Department of Computer Science <br>
at the University of Massachusetts 
</h3>

<p>
Unlike traditional data networks, future broadband-ISDN (BISDN)
wide-area networks will be required to carry a broad range of traffic
classes ranging from bursty, variable-rate sources, such as voice and
variable-rate coded video, to smooth, constant bit rate sources.
Moreover, these networks will have to do so while providing a
guaranteed performance or quality-of-service (QOS) to these traffic
classes.  The problem of characterizing performance in such networks
is thus particularly important since this must be done not only for
the traditional off-line tasks of dimensioning and design (e.g.,
determining link bandwidths, buffer capacities and processing
capacities at network switchpoints) but also for on-line, <i>
performance-driven </i> traffic control purposes such as session-level
admission control.  In this section, we outline our research aimed
at providing the analytical tools and techniques for analyzing such
networks and their diverse workloads and for designing and
characterizing the properties of scheduling policies in these
networks. 

<p>
Traditional approaches towards performance evaluation of
communication networks
are generally not
applicable in a high-speed network environment for a number of
reasons.  First, the traffic in future high-speed networks is
projected to be ``bursty,'' often processing complex correlations in
the cell arrival processes.  Simple Markovian assumptions (such as
memoryless inter-arrival times) are thus likely to be invalid in such
networks.  The gigabit rates of future high-speed networks also render
simulation ineffective for systems of any realistic size.  The very
performance metric(s) of interest in a high-speed network will also be
different -- average delay will no longer be the primary performance
measure, and, instead, <i> secondary performance measures </i> such as
probability of buffer overflow, maximum packet delay, and the tail of
delay distributions must be considered.  In this respect, there is
evidence that even relatively sophisticated performance models which
work well for predicting average delay in the presence of correlated
arrivals may be less well-suited for computing these new performance
measures of interest [Naga91].
We also note that many previous performance
evaluation techniques have been confined to studying the performance
of the <i> aggregate traffic </i> generated by a set of <i> identical </i>
sources at a <i> single </i> multiplexer in isolation; in
connection-oriented high-speed networks with QOS guarantees, it is
clear that performance must be examined on a <i> per-session </i> basis
and in a <i> network </i> setting [Kuro92,Schu92].
Finally, we note that given the
potentially complex nature of network traffic, it is becoming
increasingly valuable to be able to broadly characterize properties
(such as optimality, or near optimality) of network control mechanisms
which hold over a wide range of traffic models and assumptions.  Thus
far, however, little work has been reported on this problem for
traditional networks, much less for high-speed networks.

<p>
Given the above considerations, it is evident that new performance
evaluation techniques will be required for the design and analysis
future high-speed networks.  Furthermore, given the QOS requirements
of such emerging standards as ATM, these techniques will also be
needed for <i> on-line </i> performance driven, traffic control purposes
such as session-level admission control.  Our research in
these areas is aimed at addressing this need.  Our research divides
broadly into four areas:

<ul>
<li>
We are developing a methodology for obtaining tight pessimistic
bounds on the per-session performance of a collection of heterogeneous
sessions within a high-speed network [Kuro92].
The metrics of interest are
<i> the distribution of the packet delay and the probability of
buffer overflow.</i>  Our research is unique in that we are
interested in computing provable performance <i> bounds </i>, and in doing so
on a <i> per-session </i> basis in a very general <i> network </i> setting
in which sessions may traverse a number of hops.  This methodology
is useful, not only for the purpose of analyzing session- and
network-level performance, but also as a mechanism to be used for call
admission where performance (QOS) guarantees are to be provided.
<li>
We conjecture that the bounds computed using the above methodology may
sometimes be too loose to be of practical interest.  In these cases,
it will be of interest to compute performance, albeit in an
approximate manner, once again -- in a <i> network </i> setting. 
We have thus also examined a number of
approximate approaches towards evaluating the performance of
heterogeneous sessions within a high-speed network
[Schu91,Naga91,Schu92].  The primary
performance metric of interest is probability of buffer
overflow.  Our research here is noteworthy in considering
heterogeneous sources and in doing so in a network setting.
<li>
We have developed a methodology for designing and analyzing the
qualitative behavior of scheduling policies.
This is based
on 
sample path analysis and the theory of majorization 
[Tows90].  Our
focus is on a wide class of performance metrics, including the
average and maximum packet delay, the probability of buffer overflow,
and the length of a buffer overflow burst.  As discussed above, this
work is of particular interest and value in that it can characterize
properties of scheduling mechanisms (such as their optimality, or near 
optimality) over a wide range of assumptions, thus obviating the need
for a potentially time-consuming and/or difficult case-by-case
performance analysis. 
<li> We are also developing <i> routing policies</i> for 
   high-speed networks [Hwan91,Hwan92].  Given the need to
   provide QOS guarantees to admitted sessions (and thus implicitly
   ``reserve'' resources for on-going calls), the routing problem in
   high-speed networks shares much more in common with circuit-switched
   routing algorithms than with 
   routing in traditional data communication networks.
   Our research in [Hwan92,Hwan92a] is aimed at
   exploiting the similarities with routing in traditional circuit-switched 
   networks and adapting these policies for the case
   of high-speed ATM networks.  Of particular interest is the
   fact that ATM routing will be more processing intensive [Hwan92],
   and will be required to route traffic with heterogeneous
   bandwidth requirements [Hwan92a].
</ul>

<p>
<b> BIBLIOGRAPHY </b>

<p> <b> [Bacc92] </b> 
  F. Baccelli, Z. Liu, D. Towsley, ``Optimal Scheduling of Parallel
  Processing Systems With and Without Real-Time Constraints'', to
  appear in <i> Journal of the ACM. </i>
<p> <b> [Chip89] </b>  R. Chipalkatti, J.F. Kurose, and D. Towsley,
  ``Scheduling Policies for Real-Time and Non-Real-Time Traffic
   in a Statistical Multiplexer,''
   <i> Proc. IEEE Infocom'89, </i> (Ottawa Canada), pp. 774-783.
<p> <b> [Goli90] </b> P. Goli, J. Kurose, and D. Towsley,
  ``Approximate Minimum Laxity Scheduling Algorithms for Real-Time
  Systems,'' Technical Report 90-88, Department of Computer and
  Information Science, University of Massachusetts, Amherst, MA.
<p> <b> [Hong89] </b> J. Hong, X. Tan, and D. Towsley, ``A Performance Analysis of
   Minimum Laxity and Earliest Deadline Scheduling in a Real-Time System,''
  <i> IEEE Transactions on Computers</i>, Vol. 38, No.~12, (December 1989),
  1736--1744.
<p> <b> [Hwan91] </b>
   R.H. Hwang and J.F. Kurose, ``On Virtual Circuit Routing and Re-Routing
        in Packet-Switched Networks,''
   <i> 1991 IEEE Int. Conf. on Communications,</i> pp. 318-323.
<p> <b> [Hwan92] </b> R. Hwang, J.F. Kurose, D. Towsley,
    ``The Effect of Processing Delay and QOS Requirements in High Speed
     Networks,''
     <i> 1992 IEEE Infocom Conference, </i> (Florence, Italy, May 1992),
     pp. 160-169.
<p> <b> [Hwan92a] </b> R. Hwang, J.F. Kurose, D. Towsley,
   ``State Dependent Routing for Multi-Rate Loss Networks,''
    to appear in <i> Proc. 1992 IEEE Globecom Conference,</i>
    (Dec. 1992, Orlando, Fla.).
<p> <b> [Kuro90] </b> J. Kurose, ``An Exact Analysis of Customer Loss Under
   Minimum Laxity Scheduling in Discrete Time Queueing Systems,''
   to appear in <i> Performance Evaluation.</i>
<p> <b> [kuro91] </b> J.F. Kurose, D. Towsley, C,.M. Krishna, `Design and
  Analysis of Processor Scheduling Policies for  Real-Time  Systems''
  <i> Foundations of Real-Time Computing: Scheduling
  and Resource Management,</i> Ed. A. VanTilborg, Kluwer Publishers, 1991.
<p> <b> [Kuro92] </b> J. Kurose, ``On Computing Per-Session Performance Bounds in
     High-Speed  Multi-hop Computer Networks,''
     1992 <i> ACM SigMetrics Conference,</i> (Newport Beach, RI, June 1992),
     pp. 128-139.

<p> 
<!WA0><a href="ftp://gaia.cs.umass.edu/pub/Lopr95:TR95-109.ps.Z">
<b>[Lopr95:TR95-109]</b></a>,
F. Lo Presti, Z.-L. Zhang, D. Towsley, 
<!WA1><a href="ftp://gaia.cs.umass.edu/pub/Lopr95:TR95-109.ps.Z">
"Bounds, Approximations and Applications for a Two-Queue GPS System",</a> 
<i>Technical Report UM-CS-95-109, Department of Computer Science,</i>
 University of 
Massachusetts, December 1995. An abridged version of the paper (<!WA2><a href="ftp://gaia.cs.umass.edu/pub/Lopr95:TwoqueueGPS.ps.Z">
Lopr95:Info96</a>) appeared in 
<!WA3><a href="http://ortega.cs.ucdavis.edu/~infocom/infocom.html">INFOCOM'96</a>,
1996.
<p>

<!WA4><a href="ftp://gaia.cs.umass.edu/pub/Lopr96:ATM_Time_Scale.ps.gz">
<b>[Lopr96:ATM_Time_Scale]</b></a>,
F. Lo Presti, Z.-L. Zhang, J. Kurose and D. Towsley, 
<!WA5><a href="ftp://gaia.cs.umass.edu/pub/Lopr96:ATM_Time_Scale.ps.gz">
"Source Time Scale and Optimal Buffer/Bandwidth Trade-off for Regulated 
Traffic in an ATM Node",</a> 
<i>Technical Report UM-CS-96-38,</i>  Department of Computer Science, 
University of Massachusetts, June 1996. 
<p>

<!WA6><A HREF="ftp://gaia.cs.umass.edu/pub/Lopr96:INFOCOM97.ps.gz">
<b>[Lopr96:INFOCOM97]</b></a>,
<I> F. Lo Presti, Z.-L. Zhang, J. Kurose and D. Towsley,
<!WA7><A HREF="ftp://gaia.cs.umass.edu/pub/Lopr96:INFOCOM97.ps.gz">
"Source Time Scale and Optimal Buffer/Bandwidth Trade-off for Regulated 
Traffic in an ATM Node", </A>
To appear in <i> Proc. IEEE INFOCOM'97,</i> Kobe, Japan, 1997.

<P>

<p> <b> [Naga91] </b>
   R. Nagarajan, J.F. Kurose, and D. Towsley, ``Approximation Techniques for
     Computing Packet Loss in Finite-Buffered Voice Multiplexers,''
     <i> IEEE Journal on  Selected Areas in Communications,</i>
     Vol. 9, No. 5 (April 1991).
<p> <b> [Naga92] </b> R. Nagarajan, J.F. Kurose, D. Towsley,
     ``On Defining, Computing and Guaranteeing Quality-of-Service in
     High-Speed Networks,''
     <i> 1992 IEEE Infocom Conference, </i> (Florence, Italy, May 1992),
     pp. 2026-2035.
<p> <b> [Nels92] </b>
  R. Nelson, D. Towsley, A.N. Tantawi. ``Performance analysis of
  parallel processing systems,'' <i> IEEE Transactions on Software
  Engineering,</i> <b> SE-14</b>, 4, 532-540, April 1988.
<p> <b> [Panw88] </b> S. Panwar, D. Towsley and J. Wolf, ``Optimal Scheduling
    Policies for a Class of Queues with Customer Deadlines to the Beginning
    of Service,'' <i> J. of the ACM,</i> Vol. 35, No. 4 (Oct. 1988),
    pp. 832-844.
<p> <b> [Ping91] </b>
     S. Pingali and J. Kurose, ``On Scheduling Two Classes of Real-Time
     Traffic with Correlated Deadlines,''  
     <i> IEEE Globecom '91 Conference,</i>  June 1991.
<p> <b> [Schu90a] </b> H.G. Schulzrinne, J.F. Kurose and D. Towsley,
  ``Congestion Control by Selective Packet Discarding for
    Real-Time Traffic in High-Speed Networks,''
    <i> Proc. IEEE Infocom'90,</i> (San Francisco, CA), pp.
    545-550.
<p> <b> [Schu90b] </b> H.G. Schulzrinne, J.F. Kurose and D. Towsley,
  ``Congestion Control for
    Real-Time Traffic in High-Speed Networks,''
    Technical Report TR89-92, Dept. of Computer and Info. Sci.,
    Univ. of Mass., Amherst, MA.
<p> <b> [Schu91] </b> H.G. Schulzrinne and J.F. Kurose,
  ``Distribution of the Loss Period for Some Queues in Continuous
    and Discrete Time,'' 
    <i> IEEE Infocom'91 Conference,</i>  pp. 1446-1455.
<p> <b> [Schu92:Voice] </b> H.G. Schulzrinne, 
  `` Voice Communication Across the Internet: A Network Voice Terminal,''
    Technical Report TR 92-50,
    Dept. of Computer Science, University of Massachusetts, Amherst MA 01003,
    July 1992.
<p> <b> [Schu92] </b> H.G. Schulzrinne, J.F. Kurose, D. Towsley,
     ``Loss Correlation for Queues with Single And Multiple Input Streams,''
      <i> 1992 IEEE Int. Conference on Communications.</i>
<p> <b> [Tows89] </b> D. Towsley and S. Panwar,
    ``Comparison of Service and Buffer Overflow Policies for Multiple Server
    Queues that Serve Customers with Deadlines,''
    COINS Technical Report 89-72, University of Massachusetts, Amherst MA,
    (July, 1989).
<p> <b> [Tows90] </b> D. Towsley, ``Applications of Sample Path Analysis Techniques
    to Communication Networks,'' <i> Proc. 4th Conference on Data 
    Communication Systems and their Performance,</i>
    Barcelona, Spain, 1990 (invited paper). 
 
<p> <!WA8><A HREF="ftp://gaia.cs.umass.edu/pub/Yate93:Per-session.ps.Z">
    <b> [Yate93] </b></A> David Yates, James Kurose, Don 
    Towsley, and Michael G. Hluchyj, 
    <!WA9><A HREF="ftp://gaia.cs.umass.edu/pub/Yate93:Per-session.ps.Z">
    ``On per-session end-to-end delay distributions and the call admission
    problem for real-time applications with QOS requirements,''</A>
    <i> ACM SIGCOMM Symposium on Communications Architectures and 
    Protocols,</i> pp 2-12, Sep., 1993 (San Francisco, CA).

<p> <!WA10><A HREF="ftp://gaia.cs.umass.edu/pub/Yate94:Per-session.ps.Z">
    <b> [Yate94] </b></A> David Yates, James Kurose, Don 
    Towsley, and Michael G. Hluchyj, 
    <!WA11><A HREF="ftp://gaia.cs.umass.edu/pub/Yate94:Per-session.ps.Z">
    ``On per-session end-to-end delay and the call admission
    problem for real-time applications with QOS requirements,''</A>
    <i> Technical Report CMPSCI 93-20, University of Massachusetts,</i> 
    May, 1994.

<p> <!WA12><a href="ftp://gaia.cs.umass.edu/pub/Zhan94:SIGCOMM94.ps.Z">
<b> [Zhan94:SIGCOMM] </b> </a>,
Z.-L. Zhang, D. Towsley, J. Kurose, 
<!WA13><a href="ftp://gaia.cs.umass.edu/pub/Zhan94:SIGCOMM94.ps.Z">
"Statistical Analysis of Generalized Processor Sharing Scheduling Discipline",</a>
<i>1994 ACM SigComm Conference.</i>
<p>


<!WA14><a href="ftp://gaia.cs.umass.edu/pub/Zhan95:GPS_JSAC.ps.Z">
<b> [Zhan95:GPS_JSAC] </b> </a>,
Z.-L. Zhang, D. Towsley, J. Kurose, 
<!WA15><a href="ftp://gaia.cs.umass.edu/pub/Zhan95:GPS_JSAC.ps.Z">
"Statistical Analysis of Generalized Processor Sharing Scheduling Discipline",</a>
<i> IEEE Journal on Selected Area in Communications</i>, "Advances in the Fundamentals
 of Networking: Part I", Vol.13, No.6, pp. 1071-1080, August 1995.
<p>


<!WA16><a href="ftp://gaia.cs.umass.edu/pub/Zhan95:TR95-10.ps.Z">
<b>[Zhan95:TR95-10]</b></a>,
Z.-L. Zhang, D. Towsley, J. Kurose, 
"Statistical Analysis of Generalized Processor Sharing Scheduling Discipline",
Technical Report UM-CS-95-10, Computer Science Department, University of 
Massachusetts, February 1995.
<p>

<!WA17><a href="ftp://gaia.cs.umass.edu/pub/Zhan95:Call_Adm.ps.Z">
<b>[Zhan95:TR95-52]</b></a>,
Z.-L. Zhang, Z. Liu, J. Kurose and D. Towsley,
<!WA18><a href="ftp://gaia.cs.umass.edu/pub/Zhan95:Call_Adm.ps.Z">
"Call Admission Control Schemes under the Generalized Processor Sharing
Scheduling Discipline",</a>
<i>  Technical Report UM-CS-95-52, Computer Science 
Department, University of Massachusetts</i>, March 1995.
An abridged version (<!WA19><a href="ftp://gaia.cs.umass.edu/pub/Zhan96:GPS-CAC.ps.Z">Zhan96:GPS-CAC</a>) to appear in <i> Telecommunication Systems.</i> 
<p>

<!WA20><a href="ftp://gaia.cs.umass.edu/pub/Zhan95:TR95-96.ps.Z">
<b>[Zhan95:TR95-96]</b></a>,
Z.-L. Zhang,
<!WA21><a href="ftp://gaia.cs.umass.edu/pub/Zhan95:TR95-96.ps.Z">
"Large Deviations and the Generalized Processor Sharing Scheduling for a
 Two-Queue Systems",
</a>
<i> Technical Report UM-CS-95-96, 
Computer Science Department,</i> University of Massachusetts, Oct. 1995.
<p>

<!WA22><a href="ftp://gaia.cs.umass.edu/pub/Zhan95:TR95-97.ps.Z">
<b>[Zhan95:TR95-97]</b></a>,
Z.-L. Zhang,
<!WA23><a href="ftp://gaia.cs.umass.edu/pub/Zhan95:TR95-97.ps.Z">
"Large Deviations and the Generalized Processor Sharing Scheduling for a
 Multiple-Queue Systems",</a>
<i> Technical Report UM-CS-95-97,</i> 
Computer Science Department, University of Massachusetts, Oct. 1995.
<p>

<!WA24><a href="ftp://gaia.cs.umass.edu/pub/Zhan96:Smoothing.ps.gz">
<b>[Zhan96:Smoothing]</b></a>,
Z.-L. Zhang, J. Kurose, J. Salehi, D. Towsley, 
<!WA25><a href="ftp://gaia.cs.umass.edu/pub/Zhan96:Smoothing.ps.gz"> 
``Smoothing, Statistical Multiplexing and Call Admission Control for Stored 
Video'',</a>
<i> Technical Report UM-CS-96-029,</i>
 Department of Computer Science, 
University of Massachusetts, February 1996. 
<p>


<!WA26><A HREF="ftp://gaia.cs.umass.edu/pub/Zhan96:JSAC-Smoothing.ps.gz">
<b>[Zhan96:JSAC-Smoothing]</b></a>,
Z.-L. Zhang, J.  Kurose, J. D. Salehi, and D. Towsley,
<!WA27><A HREF="ftp://gaia.cs.umass.edu/pub/Zhan96:JSAC-Smoothing.ps.gz">
"Smoothing, Statistical Multiplexing and Call Admission Control for
Stored Video",</A>
 Accepted for Publication (<I> JSAC Special Issue on Real-Time Video
Services in Multimedia Networks </I>).

<P>
